P49: Enumeration of the Euclidean $k$ best spanning trees in a plane with $n$ points
Input:
$n$ points in a plane
Output:
The Euclidean $k$ best spanning trees of the given points.
Complexity:
$O(k^2 n + n \log n)$ total time
Comment:
An Euclidean spanning tree in a plane is a spanning tree of the complete graph whose vertices are all given points and the weight of an edge equal to the Euclidean distance between the corresponding vertices.
P50: Enumeration of the orthogonal $k$ best spanning trees in a plane with $n$ points
Input:
$n$ points in a plane
Output:
The orthogonal $k$ best spanning trees of the given points.
Complexity:
$O(k^2 + k n \log \log (n/k) + n \log n)$ total time.
Comment:
An orthogonal spanning tree in a plane is a spanning tree of the complete graph whose vertices are all given points and the weight of an edge equal to the $L_1$ distance between the corresponding vertices.
P60: Enumeration of the Euclidean $k$ best spanning trees in a plane with $n$ points
Input:
$n$ points in a plane
Output:
The Euclidean $k$ best spanning trees of the given points.
Complexity:
$O(n \log n \log k + k \min(k, n)^{1/2})$ total time
Comment:
An Euclidean spanning tree in a plane is a spanning tree of the complete graph whose vertices are all given points and the weight of an edge equal to the Euclidean distance between the corresponding vertices.